﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SudokuGame.Sudoku
{
    /// <summary>
    /// Řešitel SUDOKU by David Janáček
    /// </summary>
    public class SudokuResolverDaj : IDisposable
    {
        /// <summary>
        /// Vyřeší zadanou hru Sudoku.
        /// </summary>
        /// <param name="game">Zadaná hra</param>
        /// <param name="showProgressAction">Metoda, do níž se pošle vždy jeden krok řešení, aby uživatel měl na co koukat. Pozor, může být null.</param>
        /// <returns>Seznam všech správných řešení</returns>
        public static List<SudokuSheet> Resolve(SudokuSheet game, SudokuProgressHandler showProgressAction)
        {
            using (SudokuResolverDaj resolver = new SudokuResolverDaj(game, showProgressAction))
            {
                return resolver._ResolveGame();
            }
        }
        /// <summary>
        /// Instanční metoda pro řešení hry. Proč instanční? 
        /// Využívám metodu _DoProgress(), která pracuje s instančními proměnnými, a s Dispose těchto proměnných (v using patternu).
        /// </summary>
        /// <returns></returns>
        private List<SudokuSheet> _ResolveGame()
        {
            Stack<Sheet> stack = new Stack<Sheet>();            // Zásobník variant, které je třeba ještě zkusit vyřešit
            stack.Push(new Sheet(this._Game));                  // Vložím zadanou hru k vyřešení
            while (stack.Count > 0)
            {
                Sheet sheet = stack.Pop();
                this._BrancheCount++;

                if (sheet.IsSolved)
                {
                    _DoProgress(sheet);
                }
                else
                {
                    _DoProgress(sheet);
                    while (!sheet.IsSolved)
                    {
                        int solvedCells = 0;

                        // Vyhledám buňky, které mají jediné řešení:
                        solvedCells = sheet.SolveStepOnePossible(this._DoProgress);
                        if (solvedCells < 0) break;             // Je tam chyba
                        if (solvedCells > 0) continue;          // Něco se vyřešilo

                        // Vyhledám buňky, jejichž některá povolená hodnota je možná jen v jedné buňce ze všech sousedních buněk:
                        solvedCells = sheet.SolveStepUnique(this._DoProgress);
                        if (solvedCells > 0) continue;          // Něco se vyřešilo

                        // Pokud máme větve, rozvětvíme se:
                        if (sheet.HasBranches)
                        {   // Žádná buňka nemá jednoznačné řešení, dosud není chyba, a máme větve dalšího vývoje?
                            List<Sheet> branches = sheet.GetBranches();
                            this._NodeCount++;
                            branches.Reverse();                 // List má varianty seřazené vzestupně (podle hodnoty v proměnném políčku). Ale do zásobníku je chci vkládat reverzně, abych jako první odebral to navrchu = tu s nejnižším číslem.
                            foreach (Sheet branche in branches)
                                stack.Push(branche);            // Varianty možného rozvoje vložím do zásobníku pro další zpracování
                            break;                              //  a s aktuální hrou skončím (vyřeší se některá z jejích variant).
                        }
                        else
                        {   // Bez řešení => konec:
                            break;
                        }
                    }
                }
            }
            return this._Result;
        }
        /// <summary>
        /// Zajistí vyvolání progresu (pokud je známá metoda showProgressAction).
        /// Zajistí přidání dané hry do resultu, pokud daná hra je IsSolved.
        /// </summary>
        /// <param name="sheet">Hra (naše řešení)</param>
        /// <param name="game">Zadání hry (externí třída, jejíž klon se posílá do progresu)</param>
        /// <param name="result">Pole výsledných vyřešených her</param>
        /// <param name="showProgressAction">Akce progresu</param>
        private void _DoProgress(Sheet sheet)
        {
            SudokuSheet current = null;
            if ((!this._SkipProgress && this._ShowProgressAction != null) || sheet.IsSolved)
                current = sheet.WriteToSudokuSheet(this._Game);

            if (!this._SkipProgress && this._ShowProgressAction != null)
            {
                SudokuProgressArgs args = new SudokuProgressArgs(current, this._NodeCount, this._BrancheCount);
                this._ShowProgressAction(this, args);
            }

            if (sheet.IsSolved)
                this._Result.Add(current);

            this._SkipProgress = false;
        }
        #region Privátní život instance (konstruktor, Dispose, proměnné) = podpora Progresu
        private SudokuResolverDaj(SudokuSheet game, SudokuProgressHandler showProgressAction)
        {
            this._Game = game;
            this._Result = new List<SudokuSheet>();
            this._ShowProgressAction = showProgressAction;
            this._SkipProgress = true;
            this._NodeCount = 0;
            this._BrancheCount = 0;
        }
        void IDisposable.Dispose()
        {
            this._Game = null;
            this._ShowProgressAction = null;
        }
        private SudokuSheet _Game;
        private List<SudokuSheet> _Result;
        private SudokuProgressHandler _ShowProgressAction;
        private bool _SkipProgress;
        /// <summary>Počet křižovatek</summary>
        private int _NodeCount;
        /// <summary>Počet cest</summary>
        private int _BrancheCount;
        #endregion
        /// <summary>
        /// Pracovní třída popisující jednu hru. Třída obsahuje téměř celé řešení, kromě řešení variantního rozvoje.
        /// </summary>
        protected class Sheet
        {
            #region Konstruktory, export dat do SudokuSheet
            /// <summary>
            /// Konstruktor z externích dat
            /// </summary>
            /// <param name="game"></param>
            public Sheet(SudokuSheet game)
            {
                this._Cells = new string[COUNT1, COUNT1];
                this._Allowed = new string[COUNT1, COUNT1];
                this._ForEach((r, c) => this._Cells[r, c] = (game[r, c].HasValue ? game[r, c].Value.ToString() : ""));
            }
            /// <summary>
            /// Konstruktor z jiné instance zdejších dat
            /// </summary>
            /// <param name="game"></param>
            public Sheet(Sheet game)
            {
                this._Cells = new string[COUNT1, COUNT1];
                this._Allowed = new string[COUNT1, COUNT1];
                this._ForEach((r, c) => this._Cells[r, c] = game._Cells[r, c]);
            }
            /// <summary>
            /// Zdejší data (this) vepíše do kopie daného objektu. Zapisuje se pouze do buněk, které nejsou fixní.
            /// </summary>
            /// <param name="game"></param>
            /// <returns></returns>
            public SudokuSheet WriteToSudokuSheet(SudokuSheet game)
            {
                SudokuSheet result = game.Clone;
                this._ForEach((r, c) =>
                    {
                        string value = this._Cells[r,c];
                        if (value.Length == 1 && !result.Cells[r, c].IsFixed)
                            result[r, c] = (Int32?)(Int32.Parse(value));
                    });
                return result;
            }
            public override string ToString()
            {
                return this.Text;
            }
            #endregion
            #region Property signalizující stav
            /// <summary>
            /// Počet vyřešených buněk. Neřeší se správnost hodnot !!!
            /// </summary>
            public int SolvedCount
            {
                get
                {
                    int solvedCount = 0;
                    this._ForEach(s => solvedCount += ((String.IsNullOrEmpty(s) || "123456789".IndexOf(s) < 0) ? 0 : 1));
                    return solvedCount;
                }
            }
            /// <summary>
            /// true, pokud všechny buňky obsahují neprázdný string. Neřeší se správnost hodnot !!!
            /// </summary>
            public bool IsSolved
            {
                get { return (this.SolvedCount == COUNT2); }
            }
            /// <summary>
            /// Vizualizace
            /// </summary>
            public string Text
            {
                get
                {
                    string result = "";
                    this._ForEach((r, c) =>
                        {
                            result += (String.IsNullOrEmpty(this._Cells[r, c]) ? " " : this._Cells[r, c].Substring(0, 1));
                            if (c == (COUNT1 - 1) && r < (COUNT1 - 1))
                                result += Environment.NewLine;
                        });
                    return result;
                }
            }
            #endregion
            #region Protected data, servisní metody nikoli pro vlastní řešení
            /// <summary>
            /// Buňky: obsahují string délky 1 pokud jsou vyřešeny, nebo string délky 0 pokud jsou prázdné
            /// </summary>
            protected string[,] _Cells;
            /// <summary>
            /// Přípustné hodnoty pro buňky, data jsou platná pouze po průchodu metodou SolveStep(), neserializují se.
            /// </summary>
            protected string[,] _Allowed;
            /// <summary>
            /// Provede danou akci pro každou souřadnici hry
            /// </summary>
            /// <param name="action"></param>
            protected void _ForEach(Action<int, int> action)
            {
                for (int r = 0; r < COUNT1; r++)
                    for (int c = 0; c < COUNT1; c++)
                        action(r, c);
            }
            /// <summary>
            /// Provede danou akci pro každou buňku hry
            /// </summary>
            /// <param name="action"></param>
            protected void _ForEach(Action<string> action)
            {
                for (int r = 0; r < COUNT1; r++)
                    for (int c = 0; c < COUNT1; c++)
                        action(this._Cells[r, c]);
            }
            #endregion
            #region Řešící algoritmus
            #region Část, která řeší jednoznačně určitelné hodnoty
            /// <summary>
            /// Pro všechny dosud nevyřešené buňky určí jejich přípustné hodnoty, a pokud pro buňku je přípustná jen jedna hodnota, vepíše ji do ní.
            /// </summary>
            /// <returns></returns>
            internal int SolveStepOnePossible(Action<Sheet> doProgress)
            {
                int solvedCells = 0;

                // Musíme se připravit i na řešení případu, kdy nenajdeme ani jednu buňku s jednoznačným řešením!
                this._BranchNodeValues = null;
                this._BranchNodeRow = null;
                this._BranchNodeColumn = null;

                bool cancel = false;
                this._ForEach((r, c) =>
                {
                    string allowed = null;
                    if (!cancel && solvedCells >= 0 && String.IsNullOrEmpty(this._Cells[r, c]))
                    {   // Pokud není chyba (po chybě už nic neřešíme), a pokud buňka na adrese [r, c] ještě není vyřešená:
                        // Zjistím, které hodnoty jsou v těch sousedních buňkách, které mají vliv na buňku [r,c] (řádek, sloupec, čtverec):
                        string unallowable = "";
                        this._ForEachAffecting(r, c, value => unallowable += value, false);

                        // Určím, které hodnoty tedy mohou být vepsány do buňky na adrese [r, c]:
                        allowed = _GetAllowable(unallowable);

                        if (allowed.Length == 0)
                        {   // Na danou pozici nelze přidat nic => tohle zadání nemá řešení:
                            // Pokud jsem v tomto kroku něco vyřešil:
                            if (solvedCells > 0)
                                // => pak přeruším další řešení, ale vrátím počet vyřešených buněk => dojde k jejich promítnutí do progresu:
                                //  a v další iteraci nenaleznu žádné nové řešení, narazím zase na tuhle buňku, a protože bude solvedCells == 0,
                                //  tak spadnu do druhé větve podmínky, a skončím s hodnotou solvedCells = -1
                                cancel = true;
                            else
                                // Pokud jsem dosud nic nevyřešil, skončím s chybou a abortuje se větev:
                                solvedCells = -1;

                            this._Cells[r, c] = "0";
                            doProgress(this);
                        }
                        else if (allowed.Length == 1)
                        {   // Na danou pozici lze přidat přesně jen jednu hodnotu => máme řešení této buňky:
                            this._Cells[r, c] = allowed;
                            doProgress(this);
                            solvedCells++;
                        }
                        else
                        {   // Lze vepsat více než jednu hodnotu - je zde jistá míra nejistoty:
                            if (this._BranchNodeValues == null || allowed.Length < this._BranchNodeValues.Length)
                            {   // Na této buňce [r,c] je nejmenší počet přípustných hodnot, tuto buňku si zvolíme jako uzel pro případné rozvětvení řešení:
                                this._BranchNodeValues = allowed;
                                this._BranchNodeRow = r;
                                this._BranchNodeColumn = c;
                            }
                        }
                    }
                    this._Allowed[r, c] = allowed;
                });
                return solvedCells;
            }
            /// <summary>
            /// Pro každou buňku, která má více možných řešení (this._Allowed) určí, 
            /// zda některá povolená hodnota je přípustná ze všech sousedních buněk jen pro danou jednu buňku.
            /// Pokud ano, pak tato jedinečná hodnota je řešením buňky.
            /// </summary>
            /// <returns></returns>
            internal int SolveStepUnique(Action<Sheet> doProgress)
            {
                int solvedCells = 0;
                this._ForEach((r, c) =>
                {
                    if (String.IsNullOrEmpty(this._Cells[r, c]) && !String.IsNullOrEmpty(this._Allowed[r, c]))
                    {   // Pokud daná buňka není vyřešena, a má uvedeny povolené hodnoty, pak ji zkusíme vyřešit:
                        string allowed = this._Allowed[r, c];
                        this._ForEachAffecting(r, c, (a, b) => _RemoveCharsFromString(this._Allowed[a,b], ref allowed), true);
                        if (allowed.Length == 1)
                        {
                            this._Cells[r, c] = allowed;
                            this._Allowed[r, c] = null;
                            doProgress(this);
                            solvedCells++;
                        }
                    }
                });
                return solvedCells;
            }
            /// <summary>
            /// Odstraní znaky vyskytující se v řetězci 1 (remove) z řetězce 2 (allowed).
            /// Například pro vstupy ("123456", "2468") bude vrácena hodnota "8", 
            /// protože ostatní znaky z řetězce allowed ("246") jsou zadány v řetězci 1 (remove) a jsou z něj tedy odebrány.
            /// </summary>
            /// <param name="remove"></param>
            /// <param name="allowed"></param>
            private static void _RemoveCharsFromString(string remove, ref string allowed)
            {
                if (String.IsNullOrEmpty(remove) || String.IsNullOrEmpty(allowed)) return;
                foreach (char c in remove)
                    allowed = allowed.Replace(c.ToString(), "");
            }
            /// <summary>
            /// Metoda vyvolá danou akci (action) pro každou buňku, která leží na souřadnici, 
            /// která ovlivňuje buňku na souřadnici [row, column].
            /// Tedy: mějme buňku na souřadnici [row, column], pak akce (action) se provede 
            /// pro buňky sousedící na daném řádku, v daném sloupci i v daném segmentu (blok 3x3),
            /// ale akce se nevolá pro souřadnice vstupní buňky.
            /// Parametrem bool allCells lze ovlivnit, zda se akce má volat o pro prázdné buňky (defaultně se pro prázdné buňky akce nevolá).
            /// </summary>
            /// <param name="row">Index řádku výchozí buňky</param>
            /// <param name="column">Index sloupce výchozí buňky</param>
            /// <param name="action">Akce volaná pro odpovídající buňky</param>
            /// <param name="allCells">true = volat i pro prázdné buňky / false = nevolat (default).</param>
            protected void _ForEachAffecting(int row, int column, Action<string> action, bool allCells)
            {
                this._ForEachAffecting(row, column, (r, c) => action(this._Cells[r, c]), allCells);
            }
            /// <summary>
            /// Metoda vyvolá danou akci (action) pro každou buňku, která leží na souřadnici, 
            /// která ovlivňuje buňku na souřadnici [row, column].
            /// Tedy: mějme buňku na souřadnici [row, column], pak akce (action) se provede 
            /// pro buňky sousedící na daném řádku, v daném sloupci i v daném segmentu (blok 3x3),
            /// ale akce se nevolá pro souřadnice vstupní buňky.
            /// Parametrem bool allCells lze ovlivnit, zda se akce má volat o pro prázdné buňky (defaultně se pro prázdné buňky akce nevolá).
            /// </summary>
            /// <param name="row">Index řádku výchozí buňky</param>
            /// <param name="column">Index sloupce výchozí buňky</param>
            /// <param name="action">Akce volaná pro odpovídající buňky</param>
            /// <param name="allCells">true = volat i pro prázdné buňky / false = nevolat (default).</param>
            protected void _ForEachAffecting(int row, int column, Action<int, int> action, bool allCells)
            {
                // Řádek - všechny sloupce:
                for (int c = 0; c < COUNT1; c++)
                    if (this._CallActionFor(row, column, row, c, allCells))
                        action(row, c);

                // Sloupec - všechny řádky:
                for (int r = 0; r < COUNT1; r++)
                    if (this._CallActionFor(row, column, r, column, allCells))
                        action(r, column);

                // Blok 3x3:
                int r1 = (row / COUNT0) * COUNT0;
                int r2 = r1 + COUNT0;
                int c1 = (column / COUNT0) * COUNT0;
                int c2 = c1 + COUNT0;
                for (int r = r1; r < r2; r++)
                    for (int c = c1; c < c2; c++)
                        if (this._CallActionFor(row, column, r, c, allCells))
                            action(r, c);
            }
            /// <summary>
            /// Určí, zda se buňka na adrese [r,c] se má zpracovat v metodě _ForEachAffecting(), 
            /// přičemž adresa výchozí buňky je [row, column] 
            /// a zpracovávat se mají buňky všechny (allCells = true) nebo jen neprázdné (allCells = false).
            /// Zásadně se nezpracovává buňka na výchozí adrese (to jest když [r,c] == [row, column]).
            /// </summary>
            /// <param name="row">Index řádku výchozí buňky</param>
            /// <param name="column">Index sloupce výchozí buňky</param>
            /// <param name="r">Index řádku testované buňky</param>
            /// <param name="c">Index sloupce testované buňky</param>
            /// <param name="allCells">true = volat i pro prázdné buňky / false = nevolat (default).</param>
            /// <returns></returns>
            private bool _CallActionFor(int row, int column, int r, int c, bool allCells)
            {
                if (row == r && column == c) return false;            // Výchozí adresa => NE
                if (allCells) return true;                            // Všechny buňky => ANO
                return (!String.IsNullOrEmpty(this._Cells[r, c]));    // Neprázdné buňky.
            }
            /// <summary>
            /// Vrátí znaky, které jsou přípustné = to jsou ty, které nejsou v daném stringu, a to pouze z hodnot vhodných pro hru.
            /// Na vstupu se mohou znaky libovolněkrát opakovat a být nesetříděné.
            /// Na výstupu se znaky neopakují a jsou setříděné.
            /// Tedy například pro vstupní string "5745398" vrátí string "126".
            /// </summary>
            /// <param name="unallowable">Nepřípustné znaky. Nesmí být null, může být empty.</param>
            /// <returns></returns>
            private string _GetAllowable(string unallowable)
            {
                string result = "";
                for (int v = 1; v <= COUNT1; v++)
                {
                    string value = v.ToString();
                    if (!unallowable.Contains(value))
                        result += value;
                }
                return result;
            }
            #endregion
            #region Část, která řeší rozvětvení hry na nejednoznačných buňkách
            /// <summary>
            /// Máme připravené nějaké větve (v daném stavu hrací plochy je více dalších mžných vývojů)?
            /// </summary>
            internal bool HasBranches
            {
                get { return (!String.IsNullOrEmpty(this._BranchNodeValues) && this._BranchNodeRow.HasValue && this._BranchNodeColumn.HasValue); }
            }
            /// <summary>
            /// Metoda vrátí soupis variant (různě vyplněné instance Sheet odvozené od this), které mohou a nemusí být řešením v dané situaci.
            /// Jde v podstatě o několik kopií this, kde na políčku větvení ([_BranchNodeRow, _BranchNodeColumn]) vepsána hodnota (jako by byla vyřešena) z hodnot uložených v _BranchNodeValues.
            /// Nsledně řešitel začne řešit tyto jednotlivé varianty hry - a uvidí se, zda povedou k řešení nebo ne.
            /// </summary>
            /// <returns></returns>
            internal List<Sheet> GetBranches()
            {
                List<Sheet> result = new List<Sheet>();
                if (this.HasBranches)
                {
                    foreach (char node in this._BranchNodeValues)
                    {
                        Sheet branche = new Sheet(this);
                        branche._Cells[this._BranchNodeRow.Value, this._BranchNodeColumn.Value] = node.ToString();
                        result.Add(branche);
                    }
                }
                return result;
            }
            /// <summary>
            /// Hodnoty, které mohou být na dané pozici. Každý znak stringu představuje možné řešení v dané buňce.
            /// V průběhu řešení zde registrujeme nejkratší možnou variantu (která je delší než 1 znak = protože jde o možné varianty, nikoli o hotové řešení).
            /// </summary>
            private string _BranchNodeValues;
            /// <summary>
            /// Souřadnice [řádek], na níž registrujeme větvení dalšího vývoje
            /// </summary>
            private Int32? _BranchNodeRow;
            /// <summary>
            /// Souřadnice [sloupec], na níž registrujeme větvení dalšího vývoje
            /// </summary>
            private Int32? _BranchNodeColumn;
            #endregion
            #endregion
            #region Konstanty
            /// <summary>3 = délka hrany malé grupy</summary>
            public const int COUNT0 = 3;
            /// <summary>9 = počet buněk v jednom směru</summary>
            public const int COUNT1 = COUNT0 * COUNT0;
            /// <summary>81 = počet buněk celkem</summary>
            public const int COUNT2 = COUNT1 * COUNT1;
            #endregion
        }
    }
}
